/**
 * 给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。
 *
 * 请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
 *
 * 你可以假设 nums1 和 nums2 不会同时为空。
 *
 */

public class Solution_04 {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        //数组长度
        int m = nums1.length;
        int n = nums2.length;
        //使短的数组作为第一个数组
        if (m > n) {
            //置换数组的引用
            int[] temp = nums1; nums1 = nums2; nums2 = temp;
            //置换m n
            int tmp = m; m = n; n = tmp;
        }
        //搜索的第一个数组的区间的前后位置，中间值：用于保持中位数两边数量相等
        int iMin = 0, iMax = m, halfLen = (m + n +1) / 2;
        //对第一个数组进行二分查找
        while (iMin <= iMax) {
            int i = (iMin + iMax) / 2;  //第一个数组被分割的位置
            int j = halfLen - i;        //第二个数组被分割的位置
            if (i < iMax && nums2[j-1] > nums1[i]) {
                iMin = i + 1;   //第一个数组搜寻的区间范围向右收缩
            }else if (i > iMin && nums1[i-1] > nums2[j]) {
                iMax = i - 1;   //搜寻的区间移动到第i个位置之后
            }else {
                //刚好位置满足条件的时候

                //求边界左边最大的数
                int maxLeft = 0;
                if (i == 0) {
                    maxLeft = nums2[j-1];
                }else if (j == 0) {
                    maxLeft = nums1[i-1];
                }else {
                    maxLeft = Math.max(nums1[i-1],nums2[j-1]);
                }
                //判断奇偶，如果是偶数个，就需要求边界右边最小的数，否则就不需要
                if ((m + n) % 2 == 1) {
                    return maxLeft;
                }

                int minRight = 0;
                if (i == m) {
                    minRight = nums2[j];
                }else if (j == n) {
                    minRight = nums1[i];
                }else {
                    minRight = Math.min(nums1[i],nums2[j]);
                }
                //一定要写2.0，避免省略小数部分导致结果不正确
                return (maxLeft + minRight) / 2.0;
            }
        }
        return 0;
    }
}
